Distributed systems employ communication protocols for reliable file transfer, window clients and servers, RPC atomic transactions, multi-media communication, etc. Layering of protocols has been known as a way of dealing with the complexity of computer communication. Layered protocols offer such significant advantages as developing and testing high-level protocols broken into small layers more rapidly that large monolithic non-layered protocols. Layered protocols are modular and can often be combined in various ways, allowing the application designer to add or remove layers depending on the properties required. In many layered systems where different protocols are substitutable for one another, application designers can select a combination of protocols most suited to their expected work load. In addition, systems such as Ensemble support changing protocol stacks underneath executing applications, so the application can tune its protocol stack to its changing work load.
Unfortunately, the convenience of having a stack of protocols is often overshadowed by the problem that layering produces a lot of overhead which, in turn, increases delays in communication. Extensively layered group communication systems where high-level protocols are often implemented by 10 or more protocol layers greatly reduce design complexity of a communication network. On the other hand, extensive layering often leads to serious performance inefficiencies.
The disadvantages of layered systems leading to performance inefficiencies consist primarily of overhead, both in computation and in message headers, caused by the abstraction barriers between layers. Because a message often has to pass through as many as 10 or more protocol layers on its way from a host to the network and from the network to a host, the overhead produced by the boundaries between the layers is often more than the actual computation being done. Different systems have reported overheads for crossing layers of up to 50 μs. Therefore, it is highly desirable to mitigate the disadvantages and to develop techniques that reduce delays by improving performance of layered protocols.
Several methods have been suggested to improve performance of layered communication protocols. One of the methods is described by Robbert van Renesse in the article “Masking the Overhead of Protocol Layering”, Proc. of the Proceedings of the 1996 ACM SIGCOMM Conference, September 1996, which article is incorporated herein by reference. In that article protocols are optimized through the use of a protocol accelerator which employs, among others, such optimization techniques as pre- and post-processing of a message in order to move computation overhead out of the common path of execution. The use of that method led to the successful reduction of communication latency, but not the computation. Pre- and post-processing was done through a layering model where handlers were broken into the operations to be done during and after messaging operations (preprocessing for the next message is appended to the post-processing of the current message). The protocol accelerator also used small connection identifiers in order to compress headers from messages and message packing techniques in order to achieve higher throughput. The use of the protocol accelerator achieved code latencies of 50 μs for protocol stacks of 5 layers. The total time required for pre- and post-processing of one message during send and receive operations is approximately 170 μs, with a header overhead of 16 bytes. This result is an improvement in comparison to code-latencies of 26 μs in Ensemble, protocol headers of 8 bytes, and total processing overhead for a receive operation followed by a send operation of 63 μs, with a protocol stack that has more than twice as many layers.
The described protocol accelerator optimization model successfully reduces communication latency, but does not decrease actual computation and layering overhead. It would also be desirable to optimize a larger class of communication protocols, including outing and total ordering protocols. Moreover, the protocol accelerator approach requires structural modifications to protocols that are effectively annotations. It would be desirable to employ such optimization that calls for significantly less annotation.
Other work on protocol optimization has been done on Integrated Layer Processing (ILP) in “Analysis of Techniques to Improve Protocol Processing latency; in Proc. of the Proceedings of the 1996 ACM SIGCOMM Conference, Stanford, September 1996,” and “RPC in the x-Kernel: Evaluating New Design Techniques; In Proc. of the Fourteenth ACM SYMP. on Operating Systems Principles, pages 91-101, Asheville, N.C., December 1993. ILP encompasses optimizations on multiple protocol layers. Much of the ILP tends to focus on integrating data manipulations across protocol layers, but not on optimizing control operations and message header compression. On the other hand, ILP advantageously compiles iteration in checksums, presentation formatting, and encryption from multiple protocol layers into a single loop to minimize memory references. Currently, none of the Ensemble protocols touch the application portion of messages. It would be desirable to provide improved optimization techniques incorporating the advantages of already developed optimizations and focusing on such aspects of protocol execution that are compatible with and orthogonal to the existing optimization methods.
The above-described disadvantages of the previously developed optimization methods make it desirable to develop compilation techniques which make layered protocols execute as fast as non-layered protocols without giving up the advantages of using modular, layered protocol suites.